package com.graph;

import java.util.*;

public class Solution721 {
    int[] father;

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        father = new int[accounts.size()];
        for (int i = 0; i < accounts.size(); i++) {
            father[i] = i;
        }
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < accounts.size(); i++) {
            List<String> list = accounts.get(i);
            for (int j = 1; j < list.size(); j++) {
                if (!map.containsKey(list.get(j))) {
                    map.put(list.get(j), i);
                } else {
                    join(i, map.get(list.get(j)));
                }
            }
        }
        HashMap<Integer, List<String>> idToEmail = new HashMap<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            int id = find(entry.getValue());
            List<String> emailList = idToEmail.getOrDefault(id, new ArrayList<>());
            emailList.add(entry.getKey());
            idToEmail.put(id, emailList);
        }
        List<List<String>> res = new ArrayList<>();
        for (Map.Entry<Integer, List<String>> entry : idToEmail.entrySet()) {
            int id = entry.getKey();
            String name = accounts.get(id).get(0);
            List<String> list = entry.getValue();
            Collections.sort(list);
            list.add(0, name);
            res.add(list);
        }
        return res;
    }

    public int find(int x) {
        if (x == father[x]) return x;
        father[x] = find(father[x]);
        return father[x];
    }

    public boolean same(int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }

    public void join(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        father[y] = x;
    }
}
